package bTree.LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 四数之和 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>res=new ArrayList<>();
        int length = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < length - 3; i++) {
            if(i!=0&&nums[i]==nums[i-1]){
                continue;
            }
            for (int j=i+1;j<length-2;j++){
                if(j!=i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                int left=j+1,right=length-1;
                while (left<right){
                    long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum==target){
                        List<Integer>path=new ArrayList<>();
                        path.add(nums[i]);
                        path.add(nums[j]);
                        path.add(nums[left]);
                        path.add(nums[right]);
                        res.add(path);
                        while (left+1<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while (right-1>left&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    } else if (sum>target) {
                        right--;
                    }else {
                        left++;
                    }
                }
            }
        }
        return res;
    }
}